package practice_2025_8_14;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    boolean[] vis;
    int n;
    ArrayList<String> strs = new ArrayList<>();
    Set<String> set = new HashSet<>();
    public ArrayList<String> Permutation (String str) {
        // 字符串所有排列
        //       a1               a2             b
        // a1 a2      a1 b      a2 a1  a2 b    b a1 ba2
        // a1 a2 b    a1 b a2   a2 a1 b a2 b a1
        //
        n = str.length();
        vis = new boolean[n];
        dfs(new StringBuilder(), str);
        return strs;
    }

    public void dfs(StringBuilder curStr, String str) {
        // 递归出口
        if (curStr.length() >= n) {
            // System.out.println(curStr.toString());
            if (!set.contains(curStr.toString())) {
                strs.add(curStr.toString());
                set.add(curStr.toString());
            }
            return;
        }
        // 继续递归
        for(int i = 0; i < str.length(); i++) {
            if (!vis[i]) {
                vis[i] = true;
                curStr.append(str.charAt(i));
                dfs(curStr, str); // 继续递归
                // 回溯
                vis[i] = false;
                curStr.delete(curStr.length() - 1, curStr.length());
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n <= 1) {
            System.out.println(1);
        } else if (n == 2) {
            System.out.println(2);
        } else {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2; // 1 1 或 2 -> 2
            int sum = 3;
            // dp[3] = dp[1] + dp[2] + 1
            // 3 -> 1 2 或 1 1 1 或 2 1 或 3 -> 4
            // dp[3] = 4, dp[3] 基础上跳 1(4), dp[2] 基础上跳2(2), dp[1] 基础上跳 3(1)
            // 4 + 2 + 1 + 1
            // dp[5] : dp[4] 基础上跳1, dp[3] 基础上跳2, dp[2] 基础上跳3, dp[1]基础上跳4 + 1
            // 4 + 2 + 1 + 1
            for(int i = 3; i <= n; i++) {
                dp[i] = sum + 1;
                sum += dp[i];
            }
            System.out.println(dp[n]);
        }
    }
}
